/*
 * (C) 2012 Sheng Yi
 * A special sort : first select the biggest numer, put it in middle position
 * then from this position, from big to small, put them left-right
 */
#include <stdio.h>

void s_sort(int input[], int n, int output[]);
void qsort(int a[], int beg, int end);
int position(int a[], int beg, int end);

int main()
{
	int input[5] = {3, 6, 1, 9, 7};
	int output[5] = {0};
	int i;
	for (i = 0; i < 5; i++)
		printf("%d ", input[i]);
	printf("\n");
	//qsort(input, 0, 4);
//	for (i = 0; i < 5; i++)
//		printf("%d ", input[i]);
//	printf("\n");

	s_sort(input, 5, output);
	for (i = 0; i < 5; i++)
		printf("%d ", output[i]);
	printf("\n");
	return 0;
}

void s_sort(int input[], int n, int output[])
{
	// first, sort the input array by desending
	// use quick sort
	qsort(input, 0, n-1);

	int i;

	// calculate the middle position
	int mid = n / 2;

	// place the elements with required
	output[mid] = input[0]; // place the biggest element
	int j = mid + 1;
	i = mid - 1;
	int cnt = 1;
	while (cnt < n-1)
	{
		output[i--] = input[cnt++];
		output[j++] = input[cnt++];
	}
	
	if (i == 0)
		output[0] = input[n - 1];
}


void qsort(int a[], int beg, int end)
{
	if (beg < end)
	{
		int pos = position(a, beg, end);
		qsort(a, beg, pos - 1);
		qsort(a, pos + 1, end);
	}
}
int position(int a[], int beg, int end)
{
	int pos = -1; // the last position which littler than a[end]
	int i;
	for (i = 0; i < end; i++)
	{
		//if (a[i] < a[end]) // asending use this
		if (a[i] > a[end])	// desending use this
		{
			pos++;

			// swap
			int temp = a[i];
			a[i] = a[pos];
			a[pos] = temp;
		}
	}

	// swap a[end] and a[pos];
	pos++;
	int temp = a[end];
	a[end] = a[pos];
	a[pos] = temp;

	return pos;
}
